// https://leetcode.cn/problems/count-vowels-permutation/description/
/**
    k维一阶问题
 */

/**
    0 1 2 3 4
    a e i o u

    a can be behind of u, i, e
    e可以在a, i后面
    i can be behind of e, o
    o can be behind of i
    u can be behind of i, o
*/
int countVowelPermutation(int n) {
    long long mod = 1e9 + 7;
    char mp[] = {'a', 'e', 'i', 'o', 'u'};
    vector<vector<long long>> dp(n + 1, vector<long long>(5, 1));
    for (int i = 2; i <= n; i++) {
        dp[i][0] = (dp[i - 1][4] + dp[i - 1][2] + dp[i - 1][1]) % mod;
        dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % mod;
        dp[i][2] = (dp[i - 1][3] + dp[i - 1][1]) % mod;
        dp[i][3] = (dp[i - 1][2]) % mod;
        dp[i][4] = (dp[i - 1][2] + dp[i - 1][3]) % mod;
    }
    long long ans = 0;
    for (int i = 0; i < 5; i++) {
        ans = (ans + dp[n][i]) % mod;
    }
    return ans;
}

/**
    可以通过矩阵快速幂加速
    其实就是说[a, e, i, o, u] * [[], [], [], [], []]就可以得到下一个的五个数
    那就看要哪些
*/

vector<vector<long long>> matmulti(const vector<vector<long long>> &a, const vector<vector<long long>> &b) {
    long long mod = 1e9 + 7;
    vector<vector<long long>> ret(a.size(), vector<long long>(b[0].size()));
    for (int i = 0; i < a.size(); i++) {
        for (int j = 0; j < b[0].size(); j++) {
            for (int k = 0; k < b.size(); k++) {
                ret[i][j] += a[i][k] * b[k][j];
                ret[i][j] %= mod;
            }
        }
    }
    return ret;
}

vector<vector<long long>> matPower(vector<vector<long long>> &a, int p) {
    long long mod = 1e9 + 7;
    vector<vector<long long>> ret = {
        {1, 0, 0, 0, 0},
        {0, 1, 0, 0, 0},
        {0, 0, 1, 0, 0},
        {0, 0, 0, 1, 0},
        {0, 0, 0, 0, 1}
    };
    while (p) {
        if (p & 1) {
            ret = matmulti(ret, a);
        }
        a = matmulti(a, a);
        p >>= 1;
    }
    return ret;
}

int countVowelPermutation(int n) {
    long long mod = 1e9 + 7;
    vector<vector<long long>> ret = {
        {0, 1, 0, 0, 0},
        {1, 0, 1, 0, 0}, 
        {1, 1, 0, 1, 1},
        {0, 0, 1, 0, 1},
        {1, 0, 0, 0, 0}
    };
    vector<vector<long long>> a = {{1, 1, 1, 1, 1}};
    a = matmulti(a, matPower(ret, n - 1));
    long long ans = 0;
    for (int i = 0; i < 5; i++) {
        ans = (ans + a[0][i]) % mod;
    }
    return ans;
}
